package _interview150;

import java.util.*;

/**
 * 56. 合并区间
 */
public class No56 {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, ((o1, o2) -> o1[0] != o2[0] ? o1[0] - o2[0] : o2[1] - o1[1]));

        int n = intervals.length;
        Deque<int[]> stack = new LinkedList<>();
        stack.add(intervals[0]);
        for (int i = 1; i < n; i++) {
            while (i < n && stack.peek()[1] >= intervals[i][0]) {
                stack.peek()[1] = Math.max(intervals[i][1], stack.peek()[1]);
                i++;
            }
            if (i < n) stack.push(intervals[i]);
        }
        int[][] ans = new int[stack.size()][2];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = stack.pop();
        }
        return ans;
    }
}
